home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / lang / c / pthd-0.000 / pthd-0 / pthd-0.7 / src_tgrep / src-match / pmatch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-15  |  12.6 KB  |  674 lines
  1. /*
  2.  * PMATCH - tell if a pattern exists in a string
  3.  *
  4.  * Usage: #include <pmatch.h>
  5.  *
  6.  *    char    *pmatch( char *pattern, char *string, int len );
  7.  *
  8.  * pattern allows certian metachars:
  9.  *            . - match any character
  10.  *            * - match 0 or more occurrences of pervious char
  11.  *            + - match 1 or more occurrences of pervious char.
  12.  *            ^ - match at begining of string
  13.  *            $ - match end of string
  14.  *            [ - start of character class
  15.  *            ] - end of character class
  16.  *            ( - start of a new pattern
  17.  *            ) - end of a new pattern
  18.  *        @(n)c - match <c> at column <n>
  19.  *            | - match either pattern
  20.  *            \ - escape any special characters
  21.  *           \c - escape any special characters
  22.  *           \o - turn on any special characters
  23.  *
  24.  * witten: Marc Staveley, Aug/82
  25.  * converted from 'B' to 'C': Marc Staveley, Apr/84.
  26.  * last modified: Marc Staveley, May/84
  27.  * Last modified: Richard Marejka, Jan/94
  28.  *
  29.  * TABS=4
  30.  */
  31.  
  32. /* Copyright (c) 1982-1993, 1994  Marc Staveley                */
  33. /* This program may be used, copied, modified, and redistributed freely */
  34. /* for ANY purpose, so long as this notice remains intact.         */
  35.  
  36. /*
  37.  * Include Files
  38.  */
  39. #include <stdio.h>
  40. #include <ctype.h>
  41. #include <stdlib.h>
  42. #include <utils.h>
  43. #include "pmatch.h"
  44.  
  45. /*
  46.  * Constants & Macros
  47.  */
  48.  
  49. #if !defined(isodigit)
  50. #define isodigit(c)    (strchr_r("01234567",(c)))
  51. #endif
  52.  
  53. #define CCL_SIZE    128        /* maximum number of chars in a class */
  54. #define ESC_CHR        '\\'
  55.  
  56. /*
  57.  * Note: The order defined here must match exactly with the _metachars string.
  58.  */
  59. #define M_END            0x0001
  60. #define M_BEGINNING        0x0002
  61. #define M_ANY            0x0004
  62. #define M_CLOSURE         0x0008
  63. #define M_CLOSURE1        0x0010
  64. #define M_CCL            0x0020
  65. #define M_RE            0x0040
  66. #define M_OR            0x0080
  67. #define M_COL            0x0100
  68. #define M_CASELESS        0x0200
  69.         /* the next two types must always be last */
  70. #define M_CHAR            0x0400
  71. #define M_NCCL            0x0800
  72. /*
  73.  * Data Declarations
  74.  */
  75. #if 0
  76. typedef struct _pattern_
  77.   {
  78.     struct _pattern_ *next;    /* ^ to next element in pattern */
  79.     unsigned int type;        /* the type of metacharacter */
  80.     char *ccl;            /* the class of characters to match */
  81.     int col;            /* character must be at column col to match */
  82.     struct _pattern_ *alt;    /* ^ to alternate element in pattern */
  83.     char c;            /* the character to match */
  84.   }
  85. PATTERN;
  86. #endif
  87.  
  88. /*
  89.  * External Declarations
  90.  */
  91. static char *_metachars = "$^.*+[(|@d";
  92.  
  93. #if 0
  94. static char *start = NULL;
  95. #endif
  96.  
  97. static unsigned int all_metas = M_END
  98.                                 | M_BEGINNING
  99.                                 | M_ANY
  100.                                 | M_CLOSURE
  101.                                 | M_CLOSURE1
  102.                                 | M_CCL
  103.                                 | M_RE
  104.                                 | M_OR
  105.                                 | M_COL
  106.                                 | M_CASELESS;
  107.  
  108.  
  109. /*
  110.  * External References
  111.  */
  112.  
  113. static char *match(char *, PATTERN *, char *);
  114.  
  115. #define WARNING printf_r /* [RW] Jan/94 */
  116. /* extern    void     warning( char *, ... ); */
  117.  
  118. /*
  119.  * PMATCH - match a pattern against a string.
  120.  *
  121.  */
  122.  
  123. char *
  124. pmatch( register PATTERN *pattern, register char *string, int *len )
  125. {
  126.   char *end;
  127.   char *start;
  128.  
  129.   start = string;        /* an anchor for ^ and @(nn) */
  130.  
  131.   for (; *string; ++string)
  132.     if( (end = match (string, pattern, start)) )
  133.       {
  134.     if (len)
  135.       *len = end - string;
  136.     return (string);
  137.       }
  138.   return (NULL);
  139. }
  140.  
  141. /*
  142.  * MATCH - decide if 'pat' is valid for 'string'
  143.  *
  144.  * Usage: char    *match( char *, PATTERN *, char * )
  145.  */
  146.  
  147. static char *
  148. match (register char *s, register PATTERN * pat, register char *start)
  149. {
  150.   char *startclosure, *end;
  151.  
  152.   for (; pat; pat = pat->next)
  153.     {
  154.       switch (pat->type)
  155.     {
  156.     case M_CHAR:        /* match a character */
  157.       if (pat->c == *s++)
  158.         continue;
  159.       break;
  160.  
  161.     case M_BEGINNING:    /* match the begining of line */
  162.       if (s == start)
  163.         continue;
  164.       break;
  165.  
  166.     case M_END:        /* match end of line    */
  167.       if (*s == '\0' || *s == '\n')
  168.         continue;
  169.       break;
  170.  
  171.     case M_ANY:        /* match any chracter */
  172.       if (*s != '\0' && *s != '\n')
  173.         {
  174.           ++s;
  175.           continue;
  176.         }
  177.       break;
  178. #if !defined(PM_DEBUG)
  179.     case M_CLOSURE:    /* this is the bitch */
  180.     case M_CLOSURE1:
  181.       startclosure = (pat->type == M_CLOSURE1) ? s + 1 : s;
  182. /*
  183.  * eat up characters
  184.  */
  185.       for (; *s && (end = match (s, pat->alt, start)); s = end)
  186.         ;
  187. /*
  188.  * try to match the rest of the line
  189.  */
  190.       for (; s >= startclosure; s--)
  191.         if ((end = match (s, pat->next, start)))
  192.           return (end);
  193.  
  194.       break;
  195.  
  196.     case M_RE:
  197.       if ((s = match (s, pat->alt, start)))
  198.         continue;
  199.       break;
  200.  
  201.     case M_OR:
  202.       if ((end = match (s, pat->next, start)) ||
  203.           (end = match (s, pat->alt, start)))
  204.         return (end);
  205.       break;
  206.  
  207.     case M_CASELESS:    /* match a case-less character */
  208.       if (pat->c == tolower (*s))
  209.         {
  210.           ++s;
  211.           continue;
  212.         }
  213.       break;
  214.  
  215.     case M_CCL:        /* match a class of characters */
  216.       if (strchr_r(pat->ccl, *s++))
  217.         continue;
  218.       break;
  219.  
  220.     case M_NCCL:        /* NOT character class */
  221.       if (*s != '\0' && !strchr_r(pat->ccl, *s))
  222.         {
  223.           ++s;
  224.           continue;
  225.         }
  226.       break;
  227.  
  228.     case M_COL:        /* see if at this column */
  229.       if (pat->col == s - start + 1)
  230.         continue;
  231.       break;
  232. #endif /* !defined(PM_DEBUG)    */
  233.     default:
  234.       WARNING ("match: can't happen\n");
  235.     }
  236.       return (NULL);
  237.  
  238.     }
  239.   return (s);
  240. }
  241.  
  242. /*
  243.  * MAKEPAT - put in special characters for pmatch()
  244.  *
  245.  */
  246.  
  247. #define IF_META(m) if( !(on_metas & (m)) ) goto normal
  248.  
  249. PATTERN *
  250. makepat (char *string, char *metas)
  251. {
  252.   PATTERN *pattern, *oldpat;
  253.   register PATTERN *pat;
  254.   char *temp, *ccl;
  255.   register char *s;
  256.   unsigned int orig_metas, on_metas, paren;
  257.   int i;
  258.  
  259.   if (!string || !*string)
  260.     return (NULL);
  261.  
  262.   if (metas != NULL)
  263.     {
  264.       register char *sp;
  265. #ifdef PM_DEBUG
  266.       WARNING ("makepat: which metas to use??\n");
  267. #endif
  268.       for (orig_metas = 0; *metas; ++metas)
  269.     {
  270.       if (!(sp = strchr_r(_metachars, *metas)))
  271.         return (NULL);
  272.  
  273.       orig_metas |= (1 << (sp - _metachars));
  274.     }
  275.     }
  276.   else
  277.     orig_metas = all_metas;
  278.  
  279.   on_metas = orig_metas;
  280.   s = string;
  281.   pattern = (PATTERN *) calloc (1, sizeof (PATTERN));
  282.   oldpat = pat = pattern;
  283.   temp = (char *) malloc_r(CCL_SIZE * sizeof (char));
  284.  
  285.   for (; *s; s++)
  286.     {
  287.       switch (*s)
  288.     {
  289.     case ESC_CHR:
  290.       ++s;
  291.       if (tolower (*s) == 'c')
  292.         {            /* take next char
  293.                    * literally */
  294.           pat->type = M_CHAR;
  295.           pat->c = *++s;
  296.         }
  297.       else if (tolower (*s) == 'o')
  298.         {
  299.           /* 
  300.              * Turn on meta meaning of next char
  301.            */
  302.           register char *sp;
  303.  
  304.           if (!(sp = strchr_r(_metachars, *++s)))
  305.         goto fail;
  306.  
  307.           on_metas |= (1 << (sp - _metachars));
  308.           continue;
  309.         }
  310.       else if (isodigit (s[0]) &&
  311.            isodigit (s[1]) && isodigit (s[2]))
  312.         {
  313.           pat->type = M_CHAR;
  314.           pat->c = (char) strtol_r(s, NULL, 8);
  315.           s += 2;
  316.         }
  317.       else
  318.         {            /* take this char literally */
  319.           pat->type = M_CHAR;
  320.           pat->c = *s;
  321.         }
  322.       break;
  323.  
  324.     case '$':        /* End Of String */
  325.       IF_META (M_END);
  326.       if (s[1] != '\0' && s[1] != '|' && s[1] != ')' && s[1] != '\n')
  327.         goto fail;
  328.  
  329.       pat->type = M_END;
  330.       break;
  331.  
  332.     case '^':        /* Beginning Of String */
  333.       IF_META (M_BEGINNING);
  334.       if (s != string && s[-1] != '|' && s[-1] != '(')
  335.         goto fail;
  336.  
  337.       pat->type = M_BEGINNING;
  338.       break;
  339.  
  340.     case '.':        /* match any char */
  341.       IF_META (M_ANY);
  342.       pat->type = M_ANY;
  343.       break;
  344.  
  345.     case '*':        /* zero or more */
  346.       IF_META (M_CLOSURE);
  347.       pat->type = M_CLOSURE;
  348.       goto closure;
  349.  
  350.     case '+':        /* one or more */
  351.       IF_META (M_CLOSURE1);
  352.       pat->type = M_CLOSURE1;
  353.     closure:
  354.       if (pat == pattern || oldpat->type & (M_CLOSURE | M_CLOSURE1))
  355.         goto fail;
  356.  
  357.       pat->alt = pat;    /* pay attention now */
  358.       {
  359.         PATTERN tmp = *pat;
  360.         *pat = *oldpat;
  361.         *oldpat = tmp;
  362.       }
  363.       pat->next = NULL;
  364.       pat = oldpat;
  365.       break;
  366.  
  367.     case '[':        /* character class */
  368.       IF_META (M_CCL);
  369.  
  370.       if (s[1] == '^')
  371.         {
  372.           pat->type = M_NCCL;
  373.           ++s;
  374.         }
  375.       else
  376.         pat->type = M_CCL;
  377.  
  378.       ccl = pat->ccl = (char *) malloc_r(CCL_SIZE * sizeof (char));
  379.  
  380.       while (1)
  381.         {
  382.           if (*++s == ESC_CHR)
  383.         {        /* take next character
  384.                    * literally */
  385.           ++s;
  386.           if (tolower (*s) == 'c')    /* SHOULD WE CHECK FOR
  387.                            * OCTAL HERE ?? */
  388.             *ccl++ = *++s;
  389.           else
  390.             *ccl++ = *s;
  391.         }
  392.           else if (*s == '-')
  393.         {        /* ranges */
  394.           if (ccl == pat->ccl || s[1] == ']')    /*not at beg. or end */
  395.             *ccl++ = *s;
  396.           else
  397.             {
  398.               if (*--ccl >= *++s)
  399.             goto fail;
  400.               for (; *ccl < *s; ++ccl)
  401.             ccl[1] = *ccl + 1;
  402.               ++ccl;
  403.             }
  404.         }
  405.           else if (*s == ']')
  406.         {        /* at the end */
  407.           *ccl = '\0';
  408.           break;
  409.         }
  410.           else if (*s == '\0')
  411.         goto fail;
  412.           else
  413.         *ccl++ = *s;
  414.         }
  415.       break;
  416.  
  417.     case '(':        /* another pattern */
  418.       IF_META (M_RE);
  419.  
  420.       i = -1;
  421.       paren = 1;
  422.  
  423.       while (1)
  424.         {
  425.           if (*++s == ESC_CHR)
  426.         {
  427.           temp[++i] = *s++;
  428.  
  429.           if (tolower (*s) == 'c')
  430.             temp[++i] = *s++;
  431.         }
  432.           else if (*s == '(')
  433.         paren++;
  434.  
  435.           else if (*s == ')' && !--paren)
  436.         break;
  437.  
  438.           else if (*s == '\0')
  439.         goto fail;
  440.  
  441.           temp[++i] = *s;
  442.         }
  443.       temp[++i] = '\0';
  444.       pat->alt = makepat (temp, metas);
  445.       pat->type = M_RE;
  446.       break;
  447.  
  448.     case '|':        /* either of two */
  449.       IF_META (M_OR);
  450.  
  451.       if (*(++s))
  452.         {
  453.           if (!(pat->alt = makepat (s, metas)))
  454.         goto fail;
  455.         }
  456.  
  457.       pat->type = M_OR;
  458.  
  459.       if (pat != pattern)
  460.         {
  461.           oldpat->next = NULL;
  462.           pat->next = pattern;
  463.         }
  464.       goto ret;
  465.  
  466.     case '@':        /* at a column */
  467.       IF_META (M_COL);
  468.  
  469.       if (*++s != '(')
  470.         goto fail;
  471.  
  472.       for (i = 0, ++s; isdigit (*s); i++)
  473.         temp[i] = *s++;
  474.  
  475.       if (*s != ')')
  476.         goto fail;
  477.  
  478.       pat->col = atoi (temp);
  479.  
  480.       if (pat->col == 0)
  481.         goto fail;
  482.  
  483.       pat->type = M_COL;
  484.       break;
  485.  
  486.     default:        /* just a character */
  487.     normal:
  488.       if (on_metas & M_CASELESS)
  489.         {
  490.           pat->type = M_CASELESS;
  491.           pat->c = tolower (*s);
  492.         }
  493.       else
  494.         {
  495.           pat->type = M_CHAR;
  496.           pat->c = *s;
  497.         }
  498.       break;
  499.     }
  500.  
  501.       oldpat = pat;
  502.       oldpat->next = pat = (PATTERN *) calloc (1, sizeof (PATTERN));
  503.       on_metas = orig_metas;
  504.     }
  505.  
  506.   oldpat->next = NULL;
  507.   free (pat);
  508. ret:
  509.   free (temp);
  510.   return (pattern);
  511.  
  512. fail:
  513. #ifdef PM_DEBUG
  514.   WARNING ("makepat: failed on char: %c\n", *s);
  515. #endif
  516.   freepat (pattern);
  517.   return (NULL);
  518. }
  519.  
  520. /*
  521.  * FREEPAT - free a pattern
  522.  */
  523.  
  524. void
  525. freepat (register PATTERN * pat)
  526. {
  527.   if (pat->next)
  528.     freepat (pat->next);
  529.  
  530.   if (pat->alt)
  531.     freepat (pat->alt);
  532.  
  533.   if (pat->ccl)
  534.     free (pat->ccl);
  535.  
  536.   free (pat);
  537.  
  538.   return;
  539. }
  540.  
  541.  
  542.  
  543.  
  544.  
  545. #ifdef TESTLIB
  546.  
  547. /*
  548.  * PRINTPAT - print out a pattern in readable form.
  549.  */
  550.  
  551. #include <stdio.h>
  552.  
  553. void
  554. printpat (PATTERN * pat)
  555. {
  556.   for (; pat; pat = pat->next)
  557.     {
  558.       switch (pat->type)
  559.     {
  560.     case M_CLOSURE:
  561.       printpat (pat->alt);
  562.       printf_r("\\O*");
  563.       break;
  564.  
  565.     case M_CLOSURE1:
  566.       printpat (pat->alt);
  567.       printf_r("\\O+");
  568.       break;
  569.  
  570.     case M_RE:
  571.       printf_r("\\O(");
  572.       printpat (pat->alt);
  573.       putchar (')');
  574.       break;
  575.  
  576.     case M_OR:
  577.       printpat (pat->next);
  578.       printf_r ("\\O|");
  579.       printpat (pat->alt);
  580.       return;
  581.  
  582.     case M_CHAR:        /* match a character */
  583.       printf_r ("\\C%c", pat->c);
  584.       break;
  585.  
  586.     case M_CASELESS:    /* match a character, ignore case */
  587.       putchar (pat->c);
  588.       break;
  589.  
  590.     case M_BEGINNING:    /* match the beginning of line */
  591.       printf_r ("\\O^");
  592.       break;
  593.  
  594.     case M_END:        /* match end of line */
  595.       printf_r ("\\O$");
  596.       break;
  597.  
  598.     case M_ANY:        /* match any chracter */
  599.       printf_r ("\\O.");
  600.       break;
  601.  
  602.     case M_CCL:        /* match a class of characters */
  603.       printf_r ("\\O[%s]", pat->ccl);
  604.       break;
  605.  
  606.     case M_NCCL:        /* NOT character class */
  607.       printf_r ("\\O[\\O^%s]", pat->ccl);
  608.       break;
  609.  
  610.     case M_COL:        /* see if we are at this column */
  611.       printf_r ("\\O@(%d)", pat->col);
  612.       break;
  613.  
  614.     default:
  615.       WARNING ("PRINTPAT: can't happen\n");
  616.     }
  617.     }
  618. }
  619.  
  620.  
  621. int
  622. main (int argc, char *argv[])
  623. {
  624. #if 0
  625.   int len;
  626.   char temp[80], *start;
  627.   PATTERN *pat;
  628.  
  629.   printf_r ("string: '%s'\n", argv[2]);
  630.  
  631.   printf_r ("pat: '%s' ==> '", argv[1]);
  632.   if ((pat = makepat (argv[1], NULL)) == NULL)
  633.     {
  634.       printf_r ("Invalid pattern syntax'\n");
  635.       exit (0);
  636.     }
  637.   printpat (pat);
  638.   printf_r ("'\n");
  639.  
  640.   if (!(start = pmatch (pat, argv[2], &len)))
  641.     printf_r ("FAILED");
  642.  
  643.   else
  644.     {
  645.       strncpy_r(temp, start, len);
  646.       printf_r ("Matched: '%s'\n", temp);
  647.     }
  648. #else
  649.  
  650.   register PATTERN *pat;
  651.   int len;
  652.   char buf[BUFSIZ];
  653.   register char *bufp = buf;
  654.   register char *s;
  655.  
  656.   if (argc != 2)
  657.     printf_r ("usage: pmatch pattern <file\n");
  658.  
  659.   pat = makepat (argv[1], NULL);
  660. #if defined(PM_DEBUG)
  661.   printpat (pat);
  662.   putchar ('\n');
  663. #endif
  664.  
  665.   while (gets (buf))
  666.     if (s = pmatch (pat, bufp, &len))
  667.       puts (bufp);
  668.  
  669.   return (0);
  670. #endif
  671. }
  672.  
  673. #endif /* TESTLIB */
  674.